//手写一个LRU算法

#include <iostream>
#include <list>
#include <unordered_map>

using namespace std;

class LRUCache
{
public:
    LRUCache(int capacity) : _capacity(capacity) {}
    ~LRUCache() {}

    int get(int key) {
        auto it = _cache.find(key);
        if (it != _cache.end()){
            //查到了
            // int ret = it->second->val;
            int ret = it->second->second;
            _list.splice(_list.begin(), _list, it->second);
            _cache[key] = _list.begin();
            return ret;
        }
        return -1;
    }
    void put(int key, int val) {
        auto it = _cache.find(key);
        if (it != _cache.end()){
            //本就有，更新节点值
            // it->second->val = val;
            it->second->second = val;
            _list.splice(_list.begin(), _list, it->second);
            _cache[key] = _list.begin();
        }else{
            //本无，插入新节点
            //若节点满，按LRU淘汰节点
            if (_list.size() == _capacity){
                // int k = _list.back().key;
                int k = _list.back().first; // key
                _list.pop_back();
                _cache.erase(k);  //_cache中记得也要删掉
            }
            // _list.push_front(CacheNode<int, int>(key, val));
            _list.push_front(pair<int, int>(key, val));
            _cache[key] = _list.begin();
        }
    }

private:
    // template <typename T1, typename T2>
    // struct CacheNode
    // {
    //     CacheNode(T1 k, T2 v) : key(k), val(v) {}
    //     ~CacheNode() {}

    //     int key;
    //     int val;
    // };

private:
    int _capacity;
    // list<CacheNode<int, int>> _list;
    list<pair<int, int>> _list;
    // unordered_map<int, list<CacheNode<int, int>>::iterator> _cache;
    unordered_map<int, list<pair<int, int>>::iterator> _cache;
};

int main()
{
    LRUCache cache(2);
    cache.put(1, 0);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // 0
    cache.put(3, 3);
    cout << cache.get(2) << endl; // -1
    cache.put(4, 4);
    cout << cache.get(1) << endl; // -1
    cout << cache.get(3) << endl; // 3
    cout << cache.get(4) << endl; // 4

    return 0;
}